后缀表达式转前缀表达式

目标

你的目标是将一个后缀表达式（逆波兰表示法）转换为等价的前缀表达式（波兰表示法），通过构建并遍历表达式树来实现。

算法

1. 构建表达式树： 从左到右处理后缀表达式，使用栈进行操作。
   • 当遇到一个操作数（例如 A、B）时，为其创建一个单节点树，并将其压入栈中。
   • 当遇到一个运算符（例如 +、*）时，从栈中弹出两棵树。第一个弹出的是右子树（T₂），第二个是左子树（T₁）。以该运算符为根节点创建一棵新树，并将其重新压回栈中。
2. 生成前缀表达式字符串： 在处理完所有标记后，栈中将保存完整的表达式树。对其进行先序遍历（根 → 左 → 右）操作，以生成最终的前缀表达式。

示例

对于后缀表达式A B + C *，该算法构建出如下表达式树：

  *
   / \
  +   C
 / \
A   B

先序遍历得到的前缀表达式为：* + A B C。

输入输出格式

输入

• 第 1 行： 一个整数N（1 ≤ N≤ 1000），表示标记的数量。
• 第 2 行： 后缀表达式，包含N个标记，用空格分隔。

标记规则

• 操作数： 单个大写字母（A至Z）。
• 运算符： 四个二元运算符：+、至、*、/。

输出

• 一行，包含对应的前缀表达式，各标记之间用空格分隔。

样例

样例 1：

5

A B + C *

* + A B C

样例 2：

7

A B C * + D /

/ + A * B C D

样例 3：

7

A B + C D - *

* + A B - C D

限制条件